MASSACHUSETTS INSTITUTE OF TECHNOLOGY
A, !♦ LABORATORY
Artificial Intelligence
Memo No. 237 - PRELIMINARY RELEASE September 1971
AN INQUIRY INTO ALGORITHMIC COMPLEXITY
Patrick E. Q'Neil*
This Research was begun at the I.8.M. Cambridge Scientific Center 1n 1968,
continued while the author was an Office of Naval Research Post Doctoral
Fellow at the M.I.T. Mathematics Department, grant N00014-67-A-0204-0034
during 1969-70; and is presently being supported by the Artificial Intelli-
gence Laboratory, a Massachusetts Institute of Technology research program
supported in part by the Advanced Research Projects Agency of the Department o1
Defense and monitored by the Office of Naval Research under Contract Number
N00014-7Q-A-0362-0002.
♦Department of Electrical Engineering, Massachusetts Institute of Technology.
Forward
This Is the first section in a proposed monograph on algorithmic com-
plexity theory. Future sections shall include: Information Theory as a
Proof Technique; Algorithms Using Linear Form Inequalities; Sane Probabil fstfc
Analyses of Algorithms* etc. Comments* suggestions, and corrections are
welcomed. Please let me know what you think.
This 1s not a limited distribution document, although I may wish to
publish 1t later* Anyone who develops an Idea based on this work to a more
advanced state is welconw to publish first. I would be very eager to see
any such result as soon as possible*
SECTION I : A FORMULATION OF BASIC CONCEPTS
SI Definition of the Problem
Many readers will recall the advent of the "Fast Fourier Series" paper
of Cooley and Tukey [12]. This paper described an algorithm to evaluate the
complex Fourier series
n ' T ik
x(j) - l A(k) ^ K J- 0,1 fi-1.
k*0
where W ■ e * ' n . The algorithm required only en log n complex additions and
multiplications to perform this evaluation, where previous methods had used
en 2 such operations. The immediate result of this discovery was a dramatic
improvement in performance of calculations which were basic in a wide spec-
trum of applications; programs which had used hours of computer time every
day could now be rewritten using the Cooley-Tukey algorithm to take only
minutes!
This improvement of an old and long accepted algorithm dramatizes the
need for a systematic study of the following problem:
THE PROBLEM OF ALGORITHMIC COMPLEXITY: Given an "important" task which may
be performed by some set of algorithms implementable on a "standard computer",
what is the "minimum time" needed to perform this task using any such
algorithm*
The concept of the "importance" of a task shall be left intuitive, but
the reader may substitute the phrase "occurring frequently in applications",
as for example the ordering of a sequence of numbers or the multiplication of
two matrices. Me shall spend a great deal of time in this section clarifying
what we mean by "standard computer" and "time taken by an algorithm".
Our eventual aim of course Is to find the best algorithm to perform each
task; but to prove that an algorithm is best for a task we must solve the
Problem of Algorithmic Complexity. As has been pointed out by a number of
researchers , notably by Jack Schwartz , there are other measures of cDnplexity
for a task: the length of the shortest program for an algorithm that per-
forms the task, the minimal size of storage used by any algorithm performing
the task, etc. With no intent to ignore these othar Measures of complexity
(indeed we cannot, see 5Z t Example l f this section}, we shall focus our
attention on the time performance of an algorithm,
In the last few years a great deal of research has been done on problems
of algorithmic complexity. At the same time, many sophisticated computer
scientists have expressed perplexity (or lodged objections) concerning both
the aims and the basic assumptions of this field of inquiry- This is probably
due to the fact that algorithmic complexity Is such a new field that little
has been written on it and misconceptions tend to arise 1n such circumstances.
In this section we shall attempt to indicate the scope of the field and
scrutinize the assumptions of commonly employed techniques of proof. We
undertake this to answer some of the objections we have mentioned, but more
importantly to clarify the basic assumptions upon which any useful theory
must be founded.
52 The "Standard" 1 Computer
Since we are attempting to present the groundwork for a theory which will
find wide applications, we would like our model for a "standard" computer to
reflect the structure of the general purpose computer* Thus we stipulate
that information shall be stored as sequences of zeroes and ones (and thereby
exclude analog computers from consideration). Me also require that the in-
formation stored should be directly accessible; any bit of information stored
in memory may be retrieved in a length of time which is constant, irrespective
of its "position" with respect to our previous access.
By imposing this requirement! of course, we eliminate the entire spectrum
of tape automata as subjects of consideration. There are drawbacks to this
step. In particular we exclude Turing machines* which are capable of per-
forming any task for which an effective procedure has been conceived „ and
are attractive to the theorist because of their simplicity of concept and
firm basis in rigor. We cannot hope to achieve comparable standards of
rigor in dealing with general purpose computers for years to come. Furthermore!
progress has already been made in studying the complexity of algorithms, using
Turing machines to good effect. We shall consider this latter point further
when we discuss the field of computational complexity. For the present, we
limit ourselves to a few remarks in defense of the assumption that lfc stardard M
computers should have direct access memory.
The paramount consideration here is that general purpose computers do
have direct access memory; our desire to reflect this fact In our model springs
from our purpose of developing a theory with wide applications, Turing
machines were developed historically to investigate the question of what
problems were effectively decidable; the time which was spent in working out
an algorithm was never a consideration. Now it 1s possible, because of the
elemental nature of the Universal Turing machine, that one might be able
to calculate a measure of Implicit complexity of a task which bore a one to
one correspondence to the minimal time needed to perform the task on any
conceivable machine. Naturally this calculation would only be possible for
tasks known to be computable, or we would have solved the halting problem*
Even if we postulate the compatibility of such an implicit complexity (which
Is far removed from present day capabilities) the following problem still
faces us: what is the one to one correspondence which will enable us to
deduce the minimal time required to perforin the task on a general purpose
computer? One cannot get out of a theory what has not been put into itJ A
general purpose computer has direct access memory* and time considerations are
highly sensitive to this fact. Hence, a model such as the standard computer
with direct access memory must be developed and studied.
Returning to our description of the standard computer, we stipulate that
memory is segmented into contiguous strings of bits, each of standard length,
which shall be called "words". We make no assumption concerning the length
of a word except to indicate that it is quite small in relation to the number
Of bits in memory (an acceptable extreme case is that of words consisting of
single bits)* The words are said to have "locations" in memory and are the
basic elements on which the machine acts; indeed It is the words which we
may assume are directly addressable, rather than the bits themselves.
The computer acts on the words by performing "elementary operations".
These are the usual machine language operations and include: zeroing a word;
moving a word from one location to another; performing logical operations on
two words such as "and", "or", "nor", etc.; performing arithmetic operations
on two words such as "add", "subtract", "multiply", "divide", etc.; comparison
of two words with a branch In the control of the "program 11 of the computer
depending on the outcome of the comparison. This is not a complete list, but
it may be filled in by any reader with machine language experience. One word
of warning , however: single instructions which act on a Afield" of words
such as moving an arbitrarily large contiguous block of memory from one
location to another can rot be thought of as elementary operations* The reason
for this is that in the present early stage of development of algorithmic
complexity, the time taken by an algorithm is often estimated by counting the
number of elementary operations the algorithm performs. The elementary opera-
tions are assumed to take about the same length of time, up to a reasonable
constant factor of multiplication, (This crude assumption is not always used:
see S. Winograd, [1]-) An instruction which acts on a field of words Is really
a machine implemented macro-instruction which may take an arbitrarily greater
time to apply than the other operations mentioned above. This automatically
excludes it from our list of elementary operations.
Now that we have Imposed a structure on the memory of our standard com-
puter by segmenting ft into words* we note that this structure is not essen-
tial to the theory we are developing! Recall that words which contained only
one bit were said to be an acceptable special case; in this circumstance the
only elementary operations are those which are normally implicit in register
arithmetic: zeroing a bit, and, nor* or, not, move, and test if bit is one
with branch* Using these we may segment core into finite length words and
create "macro -ope rations" which will emulate the elementary operations used
for words, above* While It is true that it will now take much longer to
multiply two words than to add them, the time differential is constant, a
function of the word length which is very small in comparison to the total
memory size.
In this theory we are concerned almost entirely with the asymptotic
behavior* up to a multiplication constant, of the time required by an algorithm:
e.g. the tine required to multiply two n x n matrices using the standard
method in a general purpose computer is en 3 . The constant may only be deter-
mined when one 1s confronted by a specific computer, and is best derived by
a simple test: the time taken to multiply two n x n matrices where n is
known quickly gives the value of c. The asymptotic behavior, up to a con-
stant of the time taken by an algorithm is adequately estimated by counting
the number of elementary operatfons performed. The estimate is not sensitive
to the difference between the usual machine and the one bit word machine
which emulates it. We shall continue to speak of memory as consisting of
words and we will use standard elementary operations * but we must be clear that
this 1s a convenience and not a basic assumption of the model.
The following assumption* on the other hand, Is entirely basic. In the
operation of the standard computer we stipulate that the elementary opera-
tions must be applied serially, that is, in strict consecutive order. The
necessity for this assumption for a model which purports to mirror the
behavior of general purpose computers fn common use is obvious. Drawbacks
exist however. There are special purpose computers in existence (such as
array processors) whose performance Is not restricted by this assumption.
From a standpoint of applications, the theory of algorithmic complexity
cannot afford to ignore such special purpose computers. From a more theo-
retical standpoint, the investigations of S* Wfnograd [2,3] which give
However sequential operation is canonical in the fol lowing sense: The num-
ber of connections (from memory to accumulator) grows linearly with the size
of memory if operation is sequential; for parallel processors the number of
connections must grow at a much greater rate.
lower bounds on the times to perform register arithmetic would fit in the
framework of standard computers if parallel computation were permitted. We
must, however, focus our attention on a computer with serial operation- It
1s true that we are thereby ignoring a byway of algorithmic complexity which
permits parallel operation** but the two alternative assumptions are so basic
and give rise to such different models that we feel any attempt to investigate
both in the same work would cause unnecessary confusion and complication.
We sum up the discussion above in a definition;
Definition : A "standard computer" is a sequential machine with finite direct
access binary memory.
The assumption of finite memory was made implicitly when we spoke of
finite word length which was "small in comparison to the total size of
memory"- In actual practice, we shall assume that memory 1s large enough to
hold the intermediate and final results of the algorithms we will be con-
sidering; putting this another way, we shall have to guard against considering
algorithms which require a ridiculously large amount of memory. He illustrate
this by an example.
Example 1 : We are given the task of multiplying two n x n (0*1)*
Ktrlces. He may assume that the task will be performed a tremen-
dous number of times, so that any amount of "precalculation" which will
simplify the task for a proposed algorithm is justified. We proceed
as follows: multiply all possible pairs of n x n (0.1) -ma-
trices 1n the standard way and store the results in memory- Now
given any two matrices to multiply* we need merely "look up"
the product, calculating the address wtiere the result was stored
by any of a number of schemes based on the entries of the two
matrices to be multiplied* This calculation only takes en 2
operations, which may be shown to be best possible from a stand-
point of information theory (more on this later). However we
require n 2 2 2n words of memory to store all these matrices,
which is clearly impractical for any large value of n +
There can be no hard and fast rule by which one excludes algorithms
from our theory because of memory considerations. A. Meyer and M* Fischer [4]
use a variant on the above scheme to Improve the performance of Strassen's
method 1n the multiplication of (0,1) -matrices; however they do not assume
that precalculation 1s "free -1 * so their variant has intrinsic value.
We note that a restriction was placed on word length: that it should
be small in comparison to the size of memory. We should at the same time
keep some coffmon- sense absolute bound on the word length, we are trying here
to abstract a model of general purpose computers which is independent of the
length of a word in a particular case; the argument given above, that we
may emulate a standard computer with words of constant length c using one
bit words, breaks down if c is allowed to grow wfthout bound. The reason
for this 1s that the parallel processing of register arithmetic must be
emulated by sequential commands, and different elementary operations such
as addition and multiplication are intrinsically different in their complexity
of computation in a serial processor (see S*A* Cook, [5]). This fact also
holds true for the parallel computation performed in registers [3|4], and
the usefulness of the concept of elementary operations would be destroyed
if word size were allowed to grow without bound.
The argument we have made in favor of restricting the size of words, that
the parallel nature of computation 1a word arithmetic is poorly simulated by
serial one bit word operations, may be viewed from a different direction. One
of our most basic assumptions 1s the serial operation of a standard computer;
permitting arbitrarily large bit strings to be operated on in parallel
weakens this assumption. I am grateful to R- Berlekamp for the following
illustrative example.
Example 2 i We are given the task of counting the number of 1-
in a string of bits which we may assu™ fits in a word, w.
Because of the seriality of computation, 1t seems intuitively
obvius that we must view each bit position In the string »
Incrementing a counter when a bit turns out to be 1 . This
Eroblera was given to machine language programmers on a 32-
it word machine, and almost every solution submitted was of
this form- However* consider the following solution.
We first define a number of constant "masks":
a-. - 10101010... 1010
b = 01010101. .-0101
ai - 11001100,,, 1100
b* = 001100110011. -.0011
where a, is a concatenation of the string
111 ,,-1000-.. ,
2 k-l 2 k-l
repeated the number of times required until a 32-bit word
has been constructed. The words br, are defined as N0T(a^
1,e. all bits are reversed. Clearly k < 5.
The following process is used:
x +■ w the word whose 1 bits we wish to count,
1 +
Proceed f +■ 1 + 1
y * x+and+a{
z «■ x+and.b*
j ^2**(i-l)
y + RIGHT SHIR j(y)
x * y + 2
If 1*LT.5, go to proceed.
It is left as a simple exercise that when the loop is exhausted*
x is the number of 1 -bits in the word w. Suppose that the word
length were N = 2^ Then the number of 1 -bits in an M bit word
would be calculated as in the process above In c log? M opera-
tions instead of the c'N one would expect from a serial search.
This example may seem startling, but is merely a demonstration of how
the assumption of serial computation may be circumvented if arbitrarily large
words are permitted. For simplicity, we shall assume that the word length
Is great enough so that, for the numbers met with in our tasks, we need take
no precautions to guard against overflow.
13 Minimal Time for an Algorithm
He speak rather glibly of the time taken by an algorithm to perform a
task, but there Is an unfortunate lack of precision 1n this concept. It
springs from the fact that the prescription of a task 1s vague: typically
we are supplied with input In a certain format (e.g.: a list to be ordered)
and the "task" is to process the input to arrive at a well-defined output
{e.g., the ordered list).
Given an algorithm to perform some task, together with a specific Input ,
the time taken by the algorithm may be arrived at empirically. However, given
a different input we may find that the time taken to perform the same algorithm
is different. Let us make ft clear that we are not making a trivial distinction
e.g.: it takes longer using most algorithms to order a list of 1000 words
than it does for a list of 10 words. We may define the task more precisely
by letting T n be the task of ordering a list of n words. Indeed we shall
usually have this dependence on a parameter n. However, even for tasks that
are defined this explicitly, algorithms may vary in their execution time
according to what input is given; this is a function of the implicit structure
of the Input. He Illustrate this idea by the following example.
Example 1 : He are given a list of n Integers X(l).X(2),...,X(n).
The task Is to order this list, so that X(l) becomes the smallest
element In the list, X(2) the second smallest, ,.., X(n) the
largest. He do this using the algorithm INTERCHANGE SORT.
PASS *
NEWPASS PASS *■ PASS + 1
I +
COUNT «- o ...Initialize for pass
PROCEED *I +■ I + 1
If X(I+1).GT.X{I)go to CHECK, else
DUMMY +■ X(I)
X(I) +■ X(I+1) ...perform interchange
X(I+1) *■ DUMMY
COUNT ■ COUNT + 1 ...count interchange
CHECK IF I.LT.n-PASS.go to PROCEED, else
IF C0UNT.EQ.0, HALT, else
IF PASS.LT.n.go to NEWPASS, else
HALT.
This algorithm Is in very common use for ordering short
lists and we shall not explain its operation. We do note
that a count is kept on the number of interchanges in each pass*
and the algorithm halts when a pass is completed with no inter-
change made. This feature is used only occasionally, and is in
fact Inefficient for most applications.
We now ask the anticipated question: how long does this algorithm take
to perform Us task? Not surprisingly, the answer depends on the form of the
input. Let us assume the array X(1) ,X(2) ,. .. p X(n) is some permutation of the
integers 1,2*.*. »n* Now if the array X consists of the integers 1,2,... t n
in reversed order, it should be clear that the maximum number, n, of passes
will be made and further that the interchange of X(I) with X{I + 1) *ill never
be "skipped" by the IF statement which precedes it. The number of eleirantary
operations In pass k 1s given by the number of elementary operations between
the statements labeled PROCEED and CHECK inclusive (I.e., seven) t multiplied
by the number of values i takes on 1n the k— pass (n-k). The remaining
statements* being outside the central loop* may be ignored as insignificant
and we estimate the number of elementary operations performed by the algorittan
with this Input as
7[(n-l) + (n-2) t ... + Z + 1] • 7 C n )( fr , 1 ) ,
On the other hand, 1f the array X consists of the integers l f 2,3,«..,n
1n increasing order, then 1n the first pass no interchanges will be made, the
count will remain zero, and we will halt after the first pass having performed
3(n-l) operations in the central loop; we add 5 to this number to get the
total number of operations performed.
As we haye stated before, the tasks we are concerned with are "parametrize*
by an integer n (multiplying n x n matrices; evaluating an n— degree poly-
nomial) and we study algorithms from a standpoint of the asymptotic behavior,
up to a wultiplicative constant, of the time they need for execution, INTER-
CHANGE SORT is an example of what we call a "high variance" algorithm: Us
asymptotic behavior is not defined* for with different inputs it may take
en to c'n* elementary operations to execute. There are two approaches in
general use to give some meaning to the concept of "the time taken" by a high
variance algorithm.
We first consider the technique of worst case analysis: what 1s the
greatest length of time that an algorithm may take when supplied with any con-
ceivable input of the right format* It is easily seen that the worst possible
input for INTERCHANGE SORT is the list of integers In Inverse order, which we
have analyzed » and the algorithm is said to take en 2 steps.
A second type of technique often employed to find the time taken by high
variance algorithms is that of probabilistic analysis. Here we assume that
all possible Inputs to an algorithm have a known probability; for each input
we evaluate the time taken by the algorithm, t (input), and we calculate the
a
expected time which the algorithm will take, E(t ). Although this calculation
may seem to be so incredibly difficult that It 1s not possible in any but the
most elementary algorithms, this impression fs incorrect; a truly beautiful
application of probabilistic analysis of this type is given in [7]. which deals
with searching in dynamically changing binary tree structured lists. In the
particular case of INTERCHANGE SORT given above, assuming all permutations of
the integers l,2,...,n are equally likely Inputs, the expected time the algorithm
will take* E(t.), is cr\ 2 steps- (We do not prove this, but it is not diffl-
cult.)
It is not at all comnon that worst case analysis and probabilistic analysis
give the same rajflnptotic time estimate , as they do in the case of INTERCHANGE
SORT* The expected time for a search in the binary tree structured list referred
to in [7] is c log 2 n, where n is the number of entries 1n the 11st; but a
worst case analysis gives en as the tin*e taken by the search algorithm! Which
estimate should one believe?
Certainly both approaches have their merits and neither should be discarded
1n favor of the other. One of the advantages of studying the expected time
to perform an algorithm of high variance type is that it gives the researcher
something to aim at: can an algorithm be found to perform the same task whose
worst time is of the same order of magnitude as the expected tii»e of the
known high variance algorithm? In the case of the binary tree structured list
search this was done! It was achieved by Adel "son-Vel 'skiy and Landis in
Hoscow and reported on with some improvements by C.C. Foster [fl]„ It Is
probably that the motivation was supplied by a probabilistic analysis carried
out by P*F. Windley [9] who developed independently many of the same results
as those in [7]. Without such an analysis, which showed the promise of binary
tree structures for sorting and searching, the improved algorithm (with worst
time for search c log 2 n) might not have been found.
There is a school of thought which holds that time estimates derived by
probabilistic analysis of algorithms serve no utilitarian purpose in application
This attitude is justified in cases where the basic assumption of probabilistic
analysis is suspect* e+g+ all inputs to an algorithm are not equally probable.
If we may assign probabilities (even though not equal) to the various pos-
sible Inputs, a probabflfstfc analysis is still feasible* however: the ex-
pected time for the execution of the algorithm can sometimes be derived.
A much more basic objection exists to probabilistic analysis estimates.
however* which is quite difficult to answer. The objection 1s to a large extent
subjective but may be expressed as follows: how can one trust an algorithm whic
has good expected time for performance? What if, while performing a sequence
of important calculations, a high variance algorithm with excellent expected
performance continually receives input which shows it down to a performance
time close to what the worst case analysis would predict? Would it not be
better to use an algorithm which has a better worst case time estimate?
Certainly, in very special cases, such as real time control applications
where time need not be optimized but only kept within an absolute bound* such
caution is justified* But consider the hash coding algorithm as it is usually
applied, where the hashing function Is not calculated wfth a particular list
of key-words in mind. A probabilistic analysis of this algorithm reveals that
under most circumstances It rivals associative memory for speed of "look-up"
of a key-word. But a worst case analysis would consider only the case where
all key-words are hashed to the same location, and the algorithm would be
assigned the same execution time as linear search, en operations- The /WL
tree structure referred to in [8] would match any key-word in at most c log n
operations, as would logarithmic search (the latter algorithm however must
be performed on an ordered 11st, which is not amenable to insertions and de-
letions). It is doubtful that many programmers would use logarithmic search
in place of hash coding, in spite of the terrible performance of hash coding
revealed by worst case analysis.
So far in §3, we have been concerned mainly wfth "high variance algorithms"
which we have treated by example. We should make this concept more concrete.
Let a be an algorithm parametrized by an integer n. Denote the time taken by
the algorithm a 1n processing some acceptable input, a, as t"(a)* Assume
a
there exists a function f(n) and two constants* Cj and c«* not depending on n t
such that:
c,f(n) < t£(a) < c 2 f (n) * (3,1)
for any acceptable Input a. Then the algorithm a Is defined as a low variance
algorithm; we say that the time taken by the algorithm is c*f(n)* Any algorithm
which does not have this property is defined as a high variance algorithm*
There are many examples of low variaree algorithms which come iimediately
to mind, but the necessity for two constants* c« and c, to bound the time taken
by an algorithm way not at first be obvious. It might seem that either an
algorithm has high variance or else the time It takes to perform its task is
independent of its input* To see that this is not so, one need merely consider
the INTERCHANGE SORT algorithm of Example 1 with all instructions containing
the variable COUNT removed. Then the number of elementary operations required
by this algorithm to sort the array (n f n-l»n-2 t ...»3 p 2,1} is about 3n a t but
to sort the array {1 ,2 m 3,*..,n~l .n), it Is about In 2 .
This is one of the major reasons that in speaking of the time taken by
an algorithm* we are concerned with asymptotic behavior only up to a constant of
multiplication! Another reason which has already been mentioned 1s that we
wish our analysis to have as much generality as possible. Our basic assumption
that all elementary operations take the same length of time is necessary for
any kind of general theory, but 1t is not precise: It Is true only up to a
multiplicative constant.
S4 Toward a More Rigorous Theory
In this section, we have tried to develop a model, called the standard
computer, which abstracts the essential features of general purpose computers
in most common use today. By "essential" of course, we mean essential to our
purpose of estimating the time taken by algorithms in Important applications.
Hopefully, it is clear to the reader that this model has been very carefully
constructed; at each point that a difference of opinion might arise, as in
the question of whether memory could be taken to be infinite, we have tried
to show fay example why one course is better than another. We could go on at
great length in this vein, as the most severe limitation we feel In this writing
Is the necessity of limiting the number of relevant examples so as not to
lose tJie Impetus of our presentation in a welter of detail.
The standard computer we have outlined seen to lack the most important
feature of a model, that of simplicity. This Ignores, however, what is probably
the most far-reaching conclusion of this section: that a one-bit word standard
computer with register arithmetic instructions, nay emulate (and be emulated
by) a standard computer with thirty or forty bit words and an extensive in-
struction set; and this without changing the asymptotic time to perform
algorithms except for the constant of multiplication. A one-b1t word standard
computer may be defined about as simply as a Turing machine, and its programing
language should be hardly more difficult. Furthermore* in the next section we
shall present one of the basic approaches to proofs 1n computational complexity:
the use of Information theory to bound below the number of yes-no questions
answered by any algorithm which performs a given task- This puts a measure of
complexity on the task and requires at least as many elementary operations to
perform the task as there are yes-no questions answered. One of the hin-
drances to this approach has been the fact that many elementary operations are
hard to put into the framework of information theory: there seem to be no
yes-no questions answered in their performance. In the more basic framework
of one- bit word standard computers, it becomes apparent that operations such
as multiplication and addition do indeed require test and branch instructions
(yes-no question)* In fact, we may formulate the instruction set of the one-
bit word computer so that the instructions "and", "or", "nor", etc* are emu-
lated by two test and branch Instructions, Thus the only elementary opera-
tions needed for a one-bit word standard computer are: set bit zero, set bit
one, move data* and test if bit is one with branch. The question of address
arithmetic requires some thought.
We do not try to develop a theory of one-bit word standard computers in
this work; 1t is felt that such an undertaking would be premature since our
model is new and may require revision. Some time for consolidation and possible
correction of these concepts should be allotted (and here we look to readers for
suggestions) before any attempt is made to codify them*
Although we shall deal mainly with many-bit word standard computers In
the following sections, we feel that the future of algorithmic complexity lies
in the study of how tasks may be performed in some basic, elemental environment
such as we have outlined* Research is presently being jointly undertaken by
L.H. Harper {U.C. at Riverside) and O.E, Savage (Brown) based on the work of
Subbotovskoya [10] and Ne£iporuk [11]. This work studies the necessary
length of the Boolean representation of specific functions; it is assumed that
the length is proportional to the time needed for evaluation, A possible
drawback to this formulation 1s that branching 1s not permitted within the
Boolean representation. This objection may be surmountable, however, and
we hold out great hope for this approach.
References for Section I
1. Wlnograd, S,» On the number of multiplications necessary to compute certain
functions, I.B.H. Research Report RC2285 (Nov. 1968).
2. — , On the time required to perform addition, Journal of the
A*C*M, 12, 2 (April 1965), 277-285,
3. — — — ■- „ On the time required to perform multiplication. Journal
of the A. CM. 14, 4 (Oct. 1967), 793-B02.
4* Meyer, A. and Fischer, M-, Boolean matrix multiplication and transitive
closure, In draft.
5. Cook, S.A,, On the minimum computation time of functions, doctoral dis-
sertation. Harvard, 1966.
6. Dreyfus, S.E., An appraisal of some shortest path algorithms* Rand
Corporation Memorandum RM-5433-PR, October 1967.
7. Hibbard, T.N., Some combinatorial properties of certain trees, with appli-
cations to searching and sorting,
8. Foster. C.C., A study of AVL trees, 6FR-12158, Goodyear Aerospace Cor*
poration. Akron, Ohio, 1965.
9. Wind ley, P.F*, Trees, forests, and rearranging, Comp. J., Vol. 3, Mo. 2,
(I960), 84-88.
10. Subbotovskaya, 8. A. », Realization of linear functions using V, 4, -,
Soviet Math. Dokl, 2 (1961), 110.
11. Neclporuk, E.I.. A Boolean Function, Soviet Math + Dokl* 7 (1966),
999-1000.
12. Cooley, J.K, and Tukey, 0*W.» An Algorithm for the machine calculation
of complex Fourier series, Mathematics of Comp. Vol. 19, Mo, 90 (1965)
297-301.